home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_06 / gotwals / multiply.cpp < prev    next >
Text File  |  1994-04-01  |  2KB  |  73 lines
  1. -------------------- M U L T I P L Y . C P P ---------------------------
  2.  
  3.  
  4. /* multiply.cpp  Multiplication of nonnegative
  5.    integers forms the radix-2^32 product of arrays
  6.    u[n] and v[m]. Returns the result in array
  7.    w[n + m]. After Knuth, volume 2, section 4.3.1
  8.    Copyright (C) 1994 John K. Gotwals
  9.    ----------------------------------------------- */
  10. void multiply(const int *u, const int *v, int *w,
  11.                int n, int m) {
  12.     int edisav, esisav;
  13.     int carry;
  14.  
  15. __asm {
  16.     mov edisav,edi      ; edi and esi must be preserved
  17.     mov esisav,esi
  18.  
  19.     ; set w[m] to w[m+n-1] to zero inclusive
  20.     mov eax,0
  21.     mov ecx,n           ; ecx = n
  22.     mov esi,w           ; esi -> w[0]
  23.     mov edx,m           ; edx = m
  24.     init:
  25.         mov [esi+edx*4],eax
  26.         inc edx
  27.     loop init
  28.  
  29.     ; rI1 = ecx = i
  30.     ; rI2 = esi = j
  31.     ; rI3 = edi = i + j
  32.     ; edx = k = carry
  33.     ; rIn are the index registers of Knuth's MIX
  34.  
  35.     mov esi,m
  36.     dec esi                   ; j = m - 1
  37.     h1:                       ; M2. zero multiplier?
  38.       mov ebx,v               ; ebx -> v[0]
  39.       mov edx,[ebx+esi*4]
  40.       cmp edx,0 ;if v[j] = 0, goto h8 and set w[j] = 0
  41.       je h8
  42.       mov ecx,n               ; M3. initialize i = n;
  43.       lea edi,[ecx+esi]       ; (i+j) = (n+j)
  44.       dec ecx                 ; i = n - 1
  45.       mov edx,0               ; k = 0
  46.       h2:                     ; M4. multiply and add
  47.         mov carry,edx
  48.         mov ebx,u
  49.         mov eax,[ebx+ecx*4] ; eax = u[i]
  50.         mov ebx,v
  51.         mul DWORD PTR[ebx+esi*4] ; edx:eax=u[i]*v[j]
  52.         mov ebx,w
  53.         add eax,[ebx+edi*4] ; add w[i+j] to lower half
  54.         adc edx,0       ; add carry bit into upper half
  55.         add eax,carry   ; add k to lower half
  56.         adc edx,0       ; add carry bit into upper half
  57.         mov [ebx+edi*4],eax ; w[i+j] = t mod 2^32
  58.                         ; where t = u[i]*v[j]+w[i+j]+k
  59.         dec edi             ; decrease i and (i+j) by 1
  60.         dec ecx             ; M5. loop on i
  61.       jge h2                ; note: edx = t/b
  62.       h8:
  63.       mov ebx,w
  64.       mov [ebx+esi*4],edx   ; w[j] = k
  65.       dec esi               ; M6. loop on j
  66.     jge h1
  67.  
  68.     mov edi, edisav         ; restore edi and esi
  69.     mov esi, esisav
  70.   }
  71. }
  72.  
  73.